股票买卖2

题目 股票买卖 II

image-a9256fa1

思路分析

可以用dp来分析

image-6e677799

在某天 要么就是手上持股要么就是没持股两种状态 而对于这两种状态 不外乎分别对应的几种操作 此时持股 可以不动也可以卖出 此时没持股 可以不动也可以买入 那么发现所有方案数是可以搜索出来的 显然也能用dp分析出一条最好的方案

贪心的写法

我一开始感觉是 在最低点买入 最高点卖出时收益最大 用单调栈+二分找到每个点右边的最远的大于它的数即可 但是考虑到可能第二个上升趋势的左端点可能会在该上升趋势的右端点之前 这样就得均衡考虑是否要把第一个上升趋势往回退一些保持全局最优 显然不可行 又成dp了

这里给出的一种方案是 只要有上升就卖 （上升前一天卖 上升当天就卖） 这样的解法之下 会与最优解等价……emm 你这哪敢写

image-8f3faf43

考虑一种方案，在每次上升的前一天购入股票，并在上升后的当天卖出的方案

if (w[i + 1] > w[i]) res += w[i + 1] - w[i];

证明贪心解 ≥最优解： 由于贪心解都是取区间长度为 1的解，因此假设存在于最优解中的某个区间 [i,j]的长度 >1

那么会出现一下三种情况：

image-6b8b4979

对应三种情形：最优解选取的区间最终点位于上方、下方、相等。

对于情形一：显然 最优解 < 贪心解

对于情形二：显然 最优解 < 贪心解

对于情形三：毫无疑问，这就是存在于贪心解中的情形，因此 贪心解 = 最优解

得证

证明贪心解 ≤最优解：

这部分无需证明，因为贪心解即是合法解，所以他的方案必定大于等于最优解

代码实现

dp

#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int f[N][2];

int n,w[N];

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>w[i];

    f[0][0]=0,f[0][1]=-0x3f3f3f;//第0天 手上没股 收益为0 手上有股显然不合法

    for(int i=1;i<=n;i++){

        f[i][0]=max(f[i-1][0],f[i-1][1]+w[i]);

        f[i][1]=max(f[i-1][0]-w[i],f[i-1][1]);

    }

    cout<<max(f[n][0],f[n][1]);

    return 0;

}

贪心

#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int n,w[N];

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>w[i];

    int res=0;

    for(int i=1;i+1<=n;i++){

        if(w[i+1]>w[i])

            res+=w[i+1]-w[i];

    }

    cout<<res;

    return 0;

}

同类题型

视频讲解

⬅️ 线性 短视 化大为小（类dp 集合分析） 🏠 00-刷题理模型 ➡️ 贪心相关模型